package com.example.question.dp.dp4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * @Date 2023-07-28
 * @Author Jonathan
 */
public class Code02_140 {
    public static void main(String[] args) {
        Code02_140 code = new Code02_140();
        List<String> list = Arrays.asList("cat", "cats", "and", "sand", "dog");
        List<String> list1 = code.wordBreak("catsanddog", list);
        System.out.println(list1);
    }


    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        this.s = s;
        this.wordDict = wordDict;
        this.result = result;
        dfs(0, "");
        return result;
    }

    private String s;
    private List<String> wordDict;
    private List<String> result;

    public void dfs(int index, String path) {
        if (s.length() == index) {
            result.add(path);
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (!wordDict.contains(str)) {
                continue;
            }
            dfs(i + 1, Objects.equals(path, "") ? str : (path + " " + str));
        }
    }


    public Boolean wordBreak1(String s, List<String> wordDict) {
        return dfs(s, 0, wordDict);
    }


    public boolean dfs(String s, int index, List<String> wordDict) {
        if (s.length() == index) {
            return true;
        }

        boolean res = false;
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (!wordDict.contains(str)) {
                continue;
            }
            res = res || dfs(s, i + 1, wordDict);
        }
        return res;
    }
}
